package cn.lbd.arithmetic.leetcode.editor.cn;
//给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
//
// candidates 中的每个数字在每个组合中只能使用一次。 
//
// 说明： 
//
// 
// 所有数字（包括目标数）都是正整数。 
// 解集不能包含重复的组合。 
// 
//
// 示例 1: 
//
// 输入: candidates = [10,1,2,7,6,1,5], target = 8,
//所求解集为:
//[
//  [1, 7],
//  [1, 2, 5],
//  [2, 6],
//  [1, 1, 6]
//]
// 
//
// 示例 2: 
//
// 输入: candidates = [2,5,2,1,2], target = 5,
//所求解集为:
//[
//  [1,2,2],
//  [5]
//] 
// Related Topics 数组 回溯算法 
// 👍 382 👎 0


import org.junit.Test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution40 {
    private static int[] x = new int[9999999]; //存放最终解向量。对照传入的数组，加1，避免数组越界
    private static List<List<Integer>> records = new ArrayList<>();

    /**
     *
     * @param candidates 数组
     * @param target  目标值
     * @return
     */
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int op[] = new int[candidates.length]; //对照传入的数组，加1，避免数组越界
        int sum = 0;
        for (int i = 0; i < candidates.length; i++) {
            sum += candidates[i];
        }
        dfs(1, 0, sum , op, candidates.length - 1, target, candidates);
        ArrayList list = new ArrayList();
        return records.parallelStream().distinct().collect(Collectors.toList());
    }

    /**
     * 给父集合去重
     * @return
     */
    /*public static List<List<Integer>> hasNoRepetition(){
        Set<List<Integer>> set = new HashSet();
        for (List<Integer> list : records) {
            list.sort(Integer::compareTo);
            set.add(list);
        }
        List<List<Integer>> lists = new ArrayList<>();
        for (List<Integer> list : set) {
            lists.add(list);
        }
        return lists;
    }*/

    /**
     * 将每轮target = 5 的方案（list）存入集合list[list]
     * @param x 每个方案的解向量
     * @param length  数组长度
     * @param candidates 数组
     */
    public static void disp(int[] x,int length,int[] candidates){
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= length; i++) {
            if (x[i] == 1){
                list.add(candidates[i]);
            }
        }
        records.add(list.parallelStream().sorted().collect(Collectors.toList()));
    }

    /**
     * 回溯框架得到 target = 5 的决策
     *
     * @param i      当前叶子层数
     * @param tw     当前集合中的总和
     * @param rw     数组中未考虑元素的和  无论每次选还是不选，rw都要减去当前待考虑的物品
     * @param op     临时解
     * @param n      数组有多少元素要决策
     * @param target 目标解
     * @param candidates 数组
     */
    public static void dfs(int i, int tw, int rw, int[] op, int n, int target, int[] candidates) {
        if (i > n) { //递归出口，如果传进来的层数从0开始，i就要大于等于n
            if (tw == target) {
                for (int i1 = 1; i1 <= n; i1++) {
                    x[i1] = op[i1];
                }
                disp(x,n,candidates);
            }
        } else {
            //左剪枝
            if (tw + candidates[i] <= target) { //如果加上正在考虑的重量超过了目标解，就没必要考虑了
                op[i] = 1;
                dfs(i + 1, tw + candidates[i], rw - candidates[i], op, n, target, candidates);
            }
            op[i] = 0;
            //右剪枝
            if (tw + rw > target) { //如果当前物品加上剩余物品（剩余物品包括当前正在考虑的物品），都达不到目标解，就没必要接着往下选取了
                dfs(i + 1, tw, rw - candidates[i], op, n, target, candidates);
            }
        }
    }

    public static void main(String[] args) {
        int[] candidates = new int[]{2,5,2,1,2};//为了对照i，数组从1开始计算，0不去管
        int target = 5;
        List<List<Integer>> lists = combinationSum2(candidates, target);
        System.out.println(lists.toString());
    }
}
//leetcode submit region end(Prohibit modification and deletion)
